{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "平衡二叉搜索树（Balanced Binary Tree）：\n",
    "\n",
    "    是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。它能在O(log n)内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    平衡因子(balance factor)：为实现AVL树，需要在树的每个节点加入一个平衡因子(balance factor)以跟踪其变化情况。\n",
    "\n",
    "    一个节点的平衡因子为其左子树的高度和右子树的高度之差，即balanceFactor=height(leftSubTree)−height(rightSubTree)。\n",
    "    如果平衡因子大于零，则子树左重(left-heavy)。如果平衡因子小于零，则子树右重(right-heavy)。如果平衡因子是零，那么树完美平衡。\n",
    "\n",
    "    为实现AVL树，定义平衡因子为-1、0或1时这个树是平衡的，一旦树的节点的平衡因子超出了这个范围，则需要将树恢复平衡。\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    一棵空树的高度为-1，只有一个根节点的树的高度为0，以后每多一层高度加1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 旋转\n",
    "\n",
    "<img src=\"AVL树的平衡.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    AVL树的旋转类型有4种， 分别是LL(left-left)旋转、LR(left-right)旋转、RR(right-right)旋转和RL(right-left)旋转。\n",
    "    \n",
    "设x代表刚插入AVL树中的结点，设A为离x最近且平衡因子更改为2的绝对值的祖先。\n",
    "    \n",
    "#### LL旋转\n",
    "\n",
    "    如下图所示，当x位于A的左子树的左子树上时，执行LL旋转。\n",
    "\n",
    "    设left为A的左子树，要执行LL旋转，将A的左指针指向left的右子结点，left的右指针指向A，将原来指向A的指针指向left。\n",
    "\n",
    "    旋转过后，将A和left的平衡因子都改为0。所有其他结点的平衡因子没有发生变化。\n",
    "<img src=\"LL旋转.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### LR旋转\n",
    "\n",
    "\n",
    "    当x位于A的左子树的右子树上时，执行LR旋转。\n",
    "\n",
    "    设left是A的左子结点，并设A的子孙结点grandchild为left的右子结点。\n",
    "\n",
    "    要执行LR旋转，将left的右子结点指向grandchild的左子结点，grandchild的左子结点指向left，A的左子结点指向grandchild的右子结点，再将grandchild的右子结点指向A，最后将原来指向A的指针指向grandchild。\n",
    "\n",
    "    执行LR旋转之后，调整结点的平衡因子取决于旋转前grandchild结点的原平衡因子值。\n",
    "\n",
    "    如果grandchild结点的原始平衡因子为+1，就将A的平衡因子设为-1，将left的平衡因子设为0。\n",
    "\n",
    "    如果grandchild结点的原始平衡因子为0，就将A和left的平衡因子都设置为0。\n",
    "\n",
    "    如果grandchild结点的原始平衡因子为-1，就将A的平衡因子设置为0，将left的平衡因子设置为+1。\n",
    "\n",
    "    在所有的情况下，grandchild的新平衡因子都是0。所有其他结点的平衡因子都没有改变。\n",
    "    \n",
    "    \n",
    "<img src=\"LR旋转.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### RR旋转\n",
    "\n",
    "    当x位于A的左子树的右子树上时，执行RR旋转。\n",
    "\n",
    "    RR旋转与LL旋转是对称的关系。\n",
    "\n",
    "    设A的右子结点为Right。要执行RR旋转，将A的右指针指向right的左子结点，right的左指针指向A，原来指向A的指针修改为指向right。\n",
    "\n",
    "    完成旋转以后，将A和left的平衡因子都修改为0。所有其他结点的平衡因子都没有改变。\n",
    "    \n",
    "<img src=\"RR旋转.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### RL旋转\n",
    "\n",
    "当x位于A的右子树的左子树上时，执行RL旋转。\n",
    "\n",
    " RL旋转与LR旋转是对称的关系。\n",
    "\n",
    "设A的右子结点为right，right的左子结点为grandchild。要执行RL旋转，将right结点的左子结点指向grandchild的右子结点，将grandchild的右子结点指向right，将A的右子结点指向grandchild的左子结点，将grandchild的左子结点指向A，最后将原来指向A的指针指向grandchild。\n",
    "\n",
    "执行RL旋转以后，调整结点的平衡因子取决于旋转前grandchild结点的原平衡因子。这里也有三种情况需要考虑：\n",
    "\n",
    "如果grandchild的原始平衡因子值为+1，将A的平衡因子更新为0，right的更新为-1；\n",
    "\n",
    "如果grandchild的原始平衡因子值为  0，将A和right的平衡因子都更新为0；\n",
    "\n",
    "如果grandchild的原始平衡因子值为-1，将A的平衡因子更新为+1，right的更新为0；\n",
    "\n",
    "在所有情况中，都将grandchild的新平衡因子设置为0。所有其他结点的平衡因子不发生改变。\n",
    "\n",
    "<img src=\"RL旋转.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 创建树的节点类\n",
    "class TreeNode(object):\n",
    "    # 初始化树的节点\n",
    "    def __init__(self, key, val, left=None, right=None, parent=None, balanceFactor=0):\n",
    "        self.key = key                                     #节点值，节点位置，索引\n",
    "        self.payload = val                                 #有效载荷，节点显示的值\n",
    "        self.leftChild = left                             #左子节点\n",
    "        self.rightChild = right                          #右子节点\n",
    "        self.parent = parent                             #父节点\n",
    "        self.balanceFactor = balanceFactor                #节点的平衡因子\n",
    "\n",
    "    # 判断是否有左子节点，若有则返回左子节点\n",
    "    def hasLeftChild(self):\n",
    "        return self.leftChild\n",
    "\n",
    "    # 判断是否有右子节点，若有则返回右子节点\n",
    "    def hasRightChild(self):\n",
    "        return self.rightChild\n",
    "\n",
    "    # 判断是否是左子节点(父节点存在，并且self与self父节点的左子节点相同)\n",
    "    def isLeftChild(self):\n",
    "        # 下面的含义是(self.parent is not None) and (self.parent.leftChild == self)\n",
    "        return self.parent and self.parent.leftChild == self\n",
    "\n",
    "    # 判断是否是右子节点\n",
    "    def isRightChild(self):\n",
    "        return self.parent and self.parent.rightChild == self\n",
    "\n",
    "    # 判断是否是根节点\n",
    "    def isRoot(self):\n",
    "        return not self.parent                             #没有父节点\n",
    "\n",
    "    # 判断是否是叶节点\n",
    "    def isLeaf(self):\n",
    "        return not (self.rightChild or self.leftChild)    #没有左右子节点\n",
    "\n",
    "    # 判断是否有子节点\n",
    "    def hasAnyChildren(self):\n",
    "        return self.rightChild or self.leftChild         #有左或右子节点\n",
    "\n",
    "    # 判断是否有2个子节点\n",
    "    def hasBothChildren(self):\n",
    "        return self.rightChild and self.leftChild         #有左右2个子节点\n",
    "\n",
    "    # 替换节点数据\n",
    "    def replaceNodeData(self, key, value, lc, rc):\n",
    "        self.key = key                                     #更新节点值\n",
    "        self.payload = value                             #更新有效载荷\n",
    "        self.leftChild = lc                             #更新左子节点\n",
    "        self.rightChild = rc                             #更新右子节点\n",
    "        if self.hasLeftChild():                            #若有左子节点\n",
    "            self.leftChild.parent = self                 #将该节点的左子节点的父节点指向self\n",
    "        if self.hasRightChild():                        #若有右子节点\n",
    "            self.rightChild.parent = self                 #将该节点的右子节点的父节点指向self\n",
    "\n",
    "    # 中序遍历\n",
    "    \"\"\"\n",
    "        只要用了yield语句，普通函数就是生成器，也是迭代器，\n",
    "        在定义过程中不需要像迭代器那样写__iter__()和__next__()方法。\n",
    "        yield语句的作用就是在调用的时候返回相应的值和作为生成器的标志。\n",
    "    \"\"\"\n",
    "    def __iter__(self):\n",
    "        if self:                                        #若当前节点存在，则\n",
    "            if self.hasLeftChild():                        #若当前节点有左子节点，则\n",
    "                for elem in self.leftChild:                #循环输出当前节点的左子树的节点值\n",
    "                    \"\"\"\n",
    "                        在for循环中，每次执行到yield时，就返回一个迭代值，\n",
    "                        且不会终止循环；下个循环时，代码从yield返回值的下一行继续返回\n",
    "                    \"\"\"\n",
    "                    yield elem                             \n",
    "            yield self.key                                 #返回当前节点值\n",
    "            if self.hasRightChild():                    #若当前节点有右子节点，则\n",
    "                for elem in self.rightChild:            #循环输出当前节点的右子树的节点值\n",
    "                    yield elem                 \n",
    "\n",
    "    # 将被删除节点的继任者拼接到被删除的节点位置\n",
    "    def spliceOut(self):\n",
    "        if self.isLeaf():                                #若被删除节点是叶节点，则无需再拼接\n",
    "            if self.isLeftChild():                        #若被删除节点是父节点的左子节点，则\n",
    "                self.parent.leftChild = None             #被删除节点为None，无需再拼接\n",
    "            else:                                        #若被删除节点是父节点的右子节点，则\n",
    "                self.parent.rightChild = None             #被删除节点为None，无需再拼接\n",
    "        elif self.hasAnyChildren():                        #若被删除节点有子节点，则\n",
    "            if self.hasLeftChild():                        #若被删除节点有左子节点，则\n",
    "                if self.isLeftChild():                    #若被删除节点是左子节点，则\n",
    "                    # 将被删除节点的父节点的左子节点指向被删除节点的左子节点\n",
    "                    self.parent.leftChild = self.leftChild  \n",
    "                else:                                    #若被删除节点是右子节点，则\n",
    "                    # 将被删除节点的父节点的右子节点指向被删除节点的左子节点\n",
    "                    self.parent.rightChild = self.leftChild \n",
    "                # 将被删除节点的左子节点的父节点指向被删除节点的父节点\n",
    "                self.leftChild.parent = self.parent         \n",
    "            else:                                        #若被删除节点没有左子节点，则被删除节点有右子节点\n",
    "                if self.isLeftChild():                    #若被删除节点是左子节点，则\n",
    "                    # 将被删除节点的父节点的左子节点指向被删除节点的右子节点\n",
    "                    self.parent.leftChild = self.rightChild \n",
    "                else:                                    #若被删除节点是右子节点，则\n",
    "                    # 将被删除节点的父节点的右子节点指向被删除节点的右子节点\n",
    "                    self.parent.rightChild = self.rightChild\n",
    "                # 将被删除节点的右子节点的父节点指向被删除节点的父节点\n",
    "                self.rightChild.parent = self.parent         \n",
    "\n",
    "    # 查找被删除节点的继任者，继任者节点最多只能有一个子节点\n",
    "    def findSuccessor(self):\n",
    "        succ = None                                     #初始化被删除节点的继任者为None\n",
    "        if self.hasRightChild():                        #若被删除节点有右子节点，则\n",
    "            succ = self.rightChild.findMin()            #获取被删除节点的右子树中的最小节点作为继任者\n",
    "        else:                                            #若被删除节点没有右子节点，则\n",
    "            if self.parent:                                #若被删除节点有父节点，则\n",
    "                if self.isLeftChild():                    #若被删除节点是父节点的左子节点，则\n",
    "                    succ = self.parent                     #被删除节点的父节点是继任者\n",
    "                else:          \n",
    "                    \"\"\"若被删除节点是父节点的右子节点，则被删除节点的继任者是其父节点的继任者，不会是被删除节点\"\"\"\n",
    "                    self.parent.rightChild = None         #暂时将None赋值给被删除节点，则继任者不会是被删除节点，方便下一行递归查找\n",
    "                    succ = self.parent.findSuccessor()    #将被删除节点的父节点的继任者作为继任者\n",
    "                    self.parent.rightChild = self         #获得继任者后，重新将被删除节点赋值给自己，以免被删除节点为None扰乱树结构\n",
    "        return succ\n",
    "\n",
    "    # 查找当前树的最小子节点，因此例是BST搜索树，左子节点的值是最小的，所以只找左子节点\n",
    "    def findMin(self):\n",
    "        current = self                                     #将自身设置为当前节点\n",
    "        while current.hasLeftChild():                    #若当前节点有左子节点，则循环\n",
    "            current = current.leftChild                 #将当前节点的左子节点作为下一个当前节点\n",
    "        return current                                     #返回最终左子节点，即此树中的最小节点 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
